package hot100;


/*
 * Author：江松
 * Date：2023/4/11 14:48
 *
 找到字符串数组中所有字母的异位词:
1，滑动窗口，因为要比对p串，所以维护一个p串为长度的窗口
然后计算这个窗口中各个字母出现次数(哈希表)是否与p串一致
复杂度O(s*26+p)


2,优化:O(s+p+26)
 */

import java.util.LinkedList;
import java.util.List;

public class Main438 {

    public List<Integer> findAnagrams(String s, String p) {
        int n=s.length(),size=p.length();
        int l=0,r=0;

        List<Integer>res=new LinkedList<>();


        int mp[]=new int[26];
        int ms[]=new int[26];
        for(int i=0;i<size;++i){
            mp[p.charAt(i)-'a']++;
        }
        while(r<n){
            ms[s.charAt(r)-'a']++;
            if(r-l+1==size){
                int i=0;
                for(;i<26;++i){
                    System.out.printf("mp:%d ms%d\n",mp[i],ms[i]);
                    if(mp[i]!=ms[i])break;
                }
                if(i==26)res.add(l);
            }
            r++;
            if(r>=size){
                ms[s.charAt(l++)-'a']--;
            }
        }
        return res;
    }
}
